package com.gxc.recursion;

/**
 * 汉诺塔问题
 */
public class Hanoi {

    public static void main(String[] args) {
        hanoi(3);
    }

    private static void hanoi(int n) {
        if (n>0) {
            func(n, "左", "中", "右");
        }
    }

    /**
     *
     * @param n
     * @param left  起始位置
     * @param mid   中间过渡位置
     * @param right 目标位置
     */
    private static void func(int n, String left, String mid, String right) {
        if (n == 1) {
            System.out.println("move 1 from " + left + " to " + right);
        } else {
            //把n-1个盘子从 left 借助 right 移动到 mid
            func(n-1, left, right, mid);
            //把n-1个盘子从 left 移动到 right
            System.out.println("move "+n+" from " + left + " to " + right);
            //把n-1个盘子从 mid 借助 left 移动到 right
            func(n-1, mid, left, right);
        }
    }

}
